import java.util.ArrayList;
import java.util.List;

public class DAY0317 {
    public char nextGreatestLetter(char[] letters, char target) {
        int length=letters.length;
        if(target>=letters[length-1]){
            return letters[0];
        }
        int low=0;
        int height=length-1;
        while (low<height){
            int mid=(height-low)/2+low;
            if(letters[mid]>target){
                height=mid;
            }else {
                low=mid+1;
            }
        }
        return letters[low];
    }

    public int mySqrt(int x) {
        int r=0;
        int l=x;
        int t=-1;
        while (r<=x){
            int mid=(l-r)/2+r;
            if((long)mid*mid<=x){
                t=mid;
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
        return t;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != r * c) {
            return nums;
        }

        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = nums[x / n][x % n];
        }
        return ans;
    }

}
